package red.book._2._4;

import edu.princeton.cs.algs4.Inversions;
import edu.princeton.cs.algs4.StdRandom;

public class KendallTau {
	// return Kendall tau distance between two permutations
    public static long distance(int[] a, int[] b) {
        if (a.length != b.length) {
            throw new IllegalArgumentException("Array dimensions disagree");
        }
        int n = a.length;

        int[] ainv = new int[n]; //值是索引
        for (int i = 0; i < n; i++)
            ainv[a[i]] = i;

        Integer[] bnew = new Integer[n]; //也是索引记录的应该是
        for (int i = 0; i < n; i++)
            bnew[i] = ainv[b[i]];

        return count(bnew);
    }
    
    public static <Key extends Comparable<Key>> long count(Key[] a) {
        Key[] b   = a.clone();
        Key[] aux = a.clone();
        long inversions = count(a, b, aux, 0, a.length - 1);
        return inversions;
    }
    
    private static <Key extends Comparable<Key>> long count(Key[] a, Key[] b, Key[] aux, int lo, int hi) {
        long inversions = 0;
        if (hi <= lo) return 0;
        int mid = lo + (hi - lo) / 2;
        inversions += count(a, b, aux, lo, mid);  
        inversions += count(a, b, aux, mid+1, hi);
        inversions += merge(b, aux, lo, mid, hi);
        return inversions;
    }
    
    private static <Key extends Comparable<Key>> long merge(Key[] a, Key[] aux, int lo, int mid, int hi) {
        long inversions = 0;

        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k]; 
        }

        // merge back to a[]
        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)                a[k] = aux[j++];
            else if (j > hi)                 a[k] = aux[i++];
            else if (less(aux[j], aux[i])) { 
            	a[k] = aux[j++]; 
            	//inversions += (mid - i + 1);
            	inversions += (mid - i + 1);
            }
            else                             a[k] = aux[i++];
        }
        return inversions;
    }
    
    private static <Key extends Comparable<Key>> boolean less(Key v, Key w) {
        return (v.compareTo(w) < 0);
    }


    // return a random permutation of size n
    public static int[] permutation(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = i;
        StdRandom.shuffle(a);
        return a;
    }

    public static void main(String[] args) {
//    	int[] a = new int[] { 0 ,3 ,1 ,6 ,2 ,5 ,4};
//        int[] b = new int[] { 1 ,0 ,3 ,6 ,4 ,2 ,5 };
    	 
        int[] a = new int[] { 0, 3, 1, 2 };
        int[] b = new int[] { 1, 0, 3, 2 };
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i] + " " + b[i]);
        }
        System.out.println("Inversions:" + distance(a, b));
    }
}
